王桂平
计算机科学与技术专业博士、副教授、硕士研究生导师。自2003年起从事大学生程序设计竞赛指导工作，带队参加过浙江省、重庆市、四川省、广东省大学生程序设计大赛，中国大学生程序设计大赛，国际大学生程序设计大赛，团体程序设计天梯赛，蓝桥杯全国软件和信息技术专业人才大赛等赛事，指导学生累计获得奖项100余项，省级奖项1000余项。
出版了《图论算法理论、实现及应用》《程序设计方法及算法导引》《C++趣味编程及算法入门》《GESP编程能力等级认证一本通(C++一级)》等多部著作；主持省部级教学研究项目5项，建设重庆市一流课程一门，以第一作者发表教学研究论文近20篇、科学研究论文30余篇（含SCI论文9篇、EI论文10篇）；主持省部级科研项目3项，参与科研项目3项。兼任多所中小学信息学奥林匹克竞赛特聘教练。
周思益
本科毕业于中国科学技术大学、博士毕业于香港科技大学，先后于斯德哥尔摩大学（一期）、神户大学（二期）从事博士后研究，现为重庆大学副教授，研究方向为宇宙学、弦理论和量子场论。知名科普作家，擅长用浅显的语言和生动的例子给孩子们讲述数学和物理知识，自2021年7月起在短视频平台发布科普视频后，全网粉丝超一百万，被网友称为“弦论女孩”。
周迎川
重庆交通大学信息科学与工程学院硕士研究生，曾获得国家励志奖学金。本科期间获得蓝桥杯全国软件和信息技术专业人才大赛C++组全国三等奖，全国大学生数学竞赛二等奖；研究生期间获得蓝桥杯大赛C++组重庆市一等奖、Python组全国三等奖。

考纲同步：严格对标电子学会等级考试、GESP & NOI竞赛大纲要求。

解题利器：80多道数学思维题 + 200多道编程实战题，揭秘隐藏在代码里的数学思维。

名师带练：300个视频精讲，即学即懂。

硬核作者：金牌教练+百万粉科普大神+算法竞赛高手。

亲爱的小朋友们，当你们打开这本书时，相信你们已经开始了C++编程的学习之旅，甚至可能正在进入算法学习的精彩阶段。你们中的许多人，或许正在为编程等级考试或信息学竞赛做准备。在学习过程中，你们可能发现了一个有趣的现象，很多编程题目都包含着丰富的数学知识，有些内容甚至超出了你们当前数学课程的进度，比如平方根、立方根、函数等概念。

你们可能会非常困惑。信息学竞赛为什么会用到这么多数学知识？参加信息学竞赛到底要掌握哪些数学知识？是不是奥数学好了，学习算法时就没有障碍了？现在我就来逐一解答这些困惑。

计算机（computer）最初就是为“计算”而设计的。世界上第一台电子计算机ENIAC诞生于1946年，当时研制计算机的目的是解决复杂的弹道计算问题。尽管现在的计算机功能非常强大，除了可以用来做科学计算，还可以用来办公、学习、娱乐，也可以运行当前各种炫酷的人工智能应用程序，但是，无论多复杂的功能，计算机都是将它们转换成各种计算。要理解和熟练应用这些计算，就需要学好数学。此外，信息学竞赛的核心是算法设计，而算法是建立在数学基础之上的。所以，信息学竞赛需要掌握很多数学知识。

信息学竞赛涉及的数学知识包括在小学阶段学的所有初等数学基础和初等几何知识，以及在小学阶段课本上基本学不到的数列问题及递推和递归、进制及进制转换、数论基础、集合论、组合数学、图论基础、树及二叉树、概率论基础、逻辑学基础、编码及译码、博弈论基础、算法及算法复杂度等。

这么多数学知识，中学生甚至小学生能掌握吗？我觉得是可以的，因为同学们只需要理解这些数学知识背后的思想和原理，不需要手工求解这些数学问题。我们的目标是根据数学原理，设计算法，编写程序，让计算机来帮我们解决这些问题。而且这些数学知识不是在学习C++和算法前就必须全部掌握的，也就是说不是预备知识，而是贯穿于C++和算法学习的整个阶段的。

以平方根为例，小学阶段的数学没法讲平方根运算，因为手工求、等是求不出来的，但同学们只要理解了平方根的含义，知道平方根是平方的相反运算，在C++程序中知道如何调用sqrt()函数求平方根就可以了。又如，组合数学中有很多复杂的排列组合问题，对小学生来说太难了，但是在信息学竞赛里主要应用的是组合数学里的一些原理，比如，加法原理、乘法原理、鸽巢原理等。

既然信息学竞赛需要掌握很多数学知识，那么同学们直接学奥数不就可以了吗？注意，C++编程与信息学竞赛中的数学不等于奥数。奥数更多的是训练学生的计算技巧和动手解决应用问题的能力，但是这些计算技巧在C++编程与信息学竞赛中完全没有用武之地。因为编程的目的之一就是把所有计算交给程序来实现，而且奥数里津津乐道的各种应用题，在信息学竞赛的试题里几乎不会出现，此外，奥数几乎不涉及算法。所以，同学们需要专门学习信息学竞赛的数学基础知识。

本书就是一本专门讲C++编程与信息学竞赛数学基础的书，既是数学书也是编程书，侧重数学原理在编程中的应用。为了降低门槛，本书把算法难度控制在基础级，只用到了枚举、模拟、递推、递归等简单算法，此外也用到C++语言标准模板库中的容器，包括位组（bitset）、集合（set）、数对（pair）等。

最后，祝小朋友们能感受到数学之美，体会到学习数学和编程的快乐，在快乐中学习。

目 录

第1章 初等数学基础

1．1 数的认识（1）——自然数、整数

1．2 数的四则运算

1．3 整数的除法：商和余数

1．4 构成像钟表一样的环状序列

1．5 倍数和因数

1．6 合数和质数

1．7 哥德巴赫猜想

1．8 大数的认识

1．9 时间和日期中的数学知识

1．10 平方和平方根、立方和立方根

1．11 幂运算

1．12 数的认识（2）——分数

1．13 数的认识（3）——小数

1．14 整数商和浮点数商

1．15 小数在计算机中无法精确表示

1．16 数的认识（4）——有理数和无理数

1．17 整数的放大与缩小

1．18 小数的放大与缩小

1．19 分数和百分数

1．20 向上取整和向下取整

1．21 取整和四舍五入

1．22 浮点数的整数商和余数

1．23 累加∑和连乘∏

1．24 上标和下标

1．25 递推

1．26 数学和生活中的循环

1．27 一些特殊的数

1．28 函数的初步认识

1．29 幂函数和指数函数

1．30 增长很快的运算：指数运算和阶乘

1．31 其他数学知识

第2章 数列问题及递推和递归

2．1 数列及相关问题

2．2 等差数列和等比数列

2．3 斐波那契数列

2．4 数列递推的例子

2．5 数学归纳法

2．6 递归和递归函数

2．7 递归方法应用实例

2．8 数列问题实例——递推和递归求解

2．9 递推和递归总结

2．10 递归存在的问题及解决方法

2．11 整数划分问题

第3章 初等几何

3．1 三角形的判定

3．2 多边形的判定

3．3 凸多边形和凹多边形

3．4 勾股定理

3．5 勾股数

3．6 锐角三角形和钝角三角形的判定

3．7 周长、面积、表面积和体积

3．8 圆周率的故事

3．9 内角和、角度和弧度

3．10 海伦—秦九韶公式

3．11 直角坐标系和距离公式

3．12 网格坐标系

3．13 从一维到二维再到三维

第4章 进制及进制转换

4．1 数位和计数单位

4．2 科学记数法及浮点数的由来

4．3 进制及十进制

4．4 二进制

4．5 二值的表示

4．6 计量数据大小的单位

4．7 八进制和十六进制

4．8 其他进制

4．9 二进制、八进制和十六进制的相互转换

4．10 其他进制转换成十进制

4．11 十进制转换成其他进制

4．12 理解整型(int， long long)的范围

4．13 位运算及应用

4．14 原码、反码、补码

4．15 标准模板库中的位组

4．16 有符号和无符号整数的溢出问题

第5章 数论基础

5．1 整除、因数和倍数

5．2 质数及筛选法

5．3 带余数除法

5．4 最大公约数理论及应用

5．5 格点问题

5．6 扩展欧几里得算法

5．7 唯一分解定理及应用

5．8 求n!的标准质因数分解式

5．9 同余理论及应用

5．10 数论倒数——a对模m的逆

5．11 同余方程及同余方程组

5．12 欧拉函数

5．13 快速幂算法

第6章 初等代数

6．1 初等代数的研究内容

6．2 单项式与多项式

6．3 一元一次方程

6．4 一元二次方程

6．5 二元一次方程组

6．6 不定方程（组）

6．7 线性方程组

6．8 矩阵和矩阵的乘法运算

第7章 集合论

7．1 集合的概念

7．2 子集及幂集

7．3 集合的运算

7．4 STL中的集合（set）

7．5 有限集的计数问题

7．6 容斥原理

7．7 元组

7．8 STL中的数对（pair）

7．9 笛卡儿积

7．10 关系

7．11 关系的表示——关系矩阵

7．12 等价关系

第8章 组合数学

8．1 加法原理和乘法原理

8．2 排列和组合

8．3 杨辉三角

8．4 全排列及排列的字典序

8．5 排列组合问题求解

8．6 特殊的排列组合问题

8．7 第二类斯特林数和Bell数

8．8 小球放盒子问题

8．9 卡特兰数列及其应用

8．10 抽屉原理（鸽巢原理）

第9章 图论基础

9．1 从哥尼斯堡七桥问题说起

9．2 无向图和有向图

9．3 完全图和有向完全图

9．4 二分图与完全二分图

9．5 顶点的度数及相关问题

9．6 路径

9．7 连通性问题

9．8 权值、有向网和无向网

9．9 图的存储

9．10 可行遍性问题

9．11 最小生成树问题

9．12 最短路径问题

第10章 树及二叉树

10．1 树的概念

10．2 二叉树

10．3 特殊的二叉树

10．4 二叉树计数问题

10．5 树和二叉树的存储

10．6 二叉树的前序、中序和后序遍历

10．7 二叉树的恢复

10．8 m叉树及相关问题

10．9 前缀、中缀、后缀表达式

第11章 概率论基础

11．1 概率

11．2 中位数

11．3 均值和期望

11．4 随机数函数

第12章 逻辑学基础

12．1 逻辑运算和逻辑型数据

12．2 逻辑学和数理逻辑

12．3 命题及真值

12．4 联结词

12．5 逻辑推理

第13章 编码及译码

13．1 从学号和身份证号说起

13．2 西文字符的编码——ASCII编码

13．3 定长编码和变长编码

13．4 Huffman编码

13．5 译码问题及前缀码

第14章 博弈论基础

14．1 从取石头游戏说起

14．2 必胜态和必败态及相互转换

14．3 尼姆(Nim)博弈游戏

第15章 算法及算法复杂度

15．1 算法的基本概念

15．2 评价算法优劣的标准

15．3 算法效率的度量及算法复杂度

15．4 算法时间复杂度的渐进分析和表示

15．5 最好、最坏和平均情况

15．6 对数运算及其运算规律

15．7 基本的算法复杂度模型

15．8 递归算法的时间复杂度

后记

附录 课程资源使用指南